package com.leetcode.algorithm.y19.m04;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import javafx.util.Pair;

/**
 * leetcode-cn.com
 * (done)36. 有效的数独
 * (done)48. 旋转图像
 * (done)8. 字符串转换整数 (atoi)
 * (done)540. 有序数组中的单一元素
 * (done)442. 数组中重复的数据
 * @author: jie.deng
 * @time: 2019年4月16日 下午7:45:51
 */
public class MySolution0418 {
    
    /**
     * 36. 有效的数独
     * 
	 * 判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
	 * 
	 * 数字 1-9 在每一行只能出现一次。
	 * 数字 1-9 在每一列只能出现一次。
	 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
	 * 
	 * 
	 * 上图是一个部分填充的有效的数独。
	 * 
	 * 数独部分空格内已填入了数字，空白格用 '.' 表示。
	 * 
	 * 示例 1:
	 * 
	 * 输入:
	 * [
	 *   ["5","3",".",".","7",".",".",".","."],
	 *   ["6",".",".","1","9","5",".",".","."],
	 *   [".","9","8",".",".",".",".","6","."],
	 *   ["8",".",".",".","6",".",".",".","3"],
	 *   ["4",".",".","8",".","3",".",".","1"],
	 *   ["7",".",".",".","2",".",".",".","6"],
	 *   [".","6",".",".",".",".","2","8","."],
	 *   [".",".",".","4","1","9",".",".","5"],
	 *   [".",".",".",".","8",".",".","7","9"]
	 * ]
	 * 输出: true
	 * 示例 2:
	 * 
	 * 输入:
	 * [
	 *   ["8","3",".",".","7",".",".",".","."],
	 *   ["6",".",".","1","9","5",".",".","."],
	 *   [".","9","8",".",".",".",".","6","."],
	 *   ["8",".",".",".","6",".",".",".","3"],
	 *   ["4",".",".","8",".","3",".",".","1"],
	 *   ["7",".",".",".","2",".",".",".","6"],
	 *   [".","6",".",".",".",".","2","8","."],
	 *   [".",".",".","4","1","9",".",".","5"],
	 *   [".",".",".",".","8",".",".","7","9"]
	 * ]
	 * 输出: false
	 * 解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
	 *      但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
	 * 说明:
	 * 
	 * 一个有效的数独（部分已被填充）不一定是可解的。
	 * 只需要根据以上规则，验证已经填入的数字是否有效即可。
	 * 给定数独序列只包含数字 1-9 和字符 '.' 。
	 * 给定数独永远是 9x9 形式的。
     * @param board
     * @return
     */
    public boolean isValidSudoku(char[][] board) {
        // 考察行
        for (int row = 0; row < 9; row++) {
            boolean[] flags = new boolean[9];
            for (int col = 0; col < 9; col++) {
                if (board[row][col] != '.') {
                    if (flags[board[row][col] - '0' - 1]) {
                        return false;
                    } else {
                        flags[board[row][col] - '0' - 1] = true;
                    }
                }
            }
        }
        // 考察列
        for (int col = 0; col < 9; col++) {
            boolean[] flags = new boolean[9];
            for (int row = 0; row < 9; row++) {
                if (board[row][col] != '.') {
                    if (flags[board[row][col] - '0' - 1]) {
                        return false;
                    } else {
                        flags[board[row][col] - '0' - 1] = true;
                    }
                }
            }
        }
        // 考察3x3宫
        List<Pair<Integer, Integer>> list = Arrays.asList(new Pair<Integer, Integer>(1, 1),
                new Pair<Integer, Integer>(1, 4), new Pair<Integer, Integer>(1, 7), new Pair<Integer, Integer>(4, 1),
                new Pair<Integer, Integer>(4, 4), new Pair<Integer, Integer>(4, 7), new Pair<Integer, Integer>(7, 1),
                new Pair<Integer, Integer>(7, 4), new Pair<Integer, Integer>(7, 7));
        for (Pair<Integer, Integer> pair : list) {
            boolean[] flags = new boolean[9];
            Integer r = pair.getKey();
            Integer c = pair.getValue();
            List<Pair<Integer, Integer>> subList = Arrays.asList(new Pair<Integer, Integer>(r - 1, c - 1),
                    new Pair<Integer, Integer>(r - 1, c), new Pair<Integer, Integer>(r - 1, c + 1),
                    new Pair<Integer, Integer>(r, c - 1), new Pair<Integer, Integer>(r, c),
                    new Pair<Integer, Integer>(r, c + 1), new Pair<Integer, Integer>(r + 1, c - 1),
                    new Pair<Integer, Integer>(r + 1, c), new Pair<Integer, Integer>(r + 1, c + 1));
            for (Pair<Integer, Integer> pair2 : subList) {
                Integer row = pair2.getKey();
                Integer col = pair2.getValue();
                if (board[row][col] != '.') {
                    if (flags[board[row][col] - '0' - 1]) {
                        return false;
                    } else {
                        flags[board[row][col] - '0' - 1] = true;
                    }
                }
            }
        }
        return true;
    }
    
    /**
     * 48. 旋转图像
     * 
	 * 给定一个 n × n 的二维矩阵表示一个图像。
	 * 
	 * 将图像顺时针旋转 90 度。
	 * 
	 * 说明：
	 * 
	 * 你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
	 * 
	 * 示例 1:
	 * 
	 * 给定 matrix = 
	 * [
	 *   [1,2,3],
	 *   [4,5,6],
	 *   [7,8,9]
	 * ],
	 * 
	 * 原地旋转输入矩阵，使其变为:
	 * [
	 *   [7,4,1],
	 *   [8,5,2],
	 *   [9,6,3]
	 * ]
	 * 示例 2:
	 * 
	 * 给定 matrix =
	 * [
	 *   [ 5, 1, 9,11],
	 *   [ 2, 4, 8,10],
	 *   [13, 3, 6, 7],
	 *   [15,14,12,16]
	 * ], 
	 * 
	 * 原地旋转输入矩阵，使其变为:
	 * [
	 *   [15,13, 2, 5],
	 *   [14, 3, 4, 1],
	 *   [12, 6, 8, 9],
	 *   [16, 7,10,11]
	 * ]
     * @param matrix
     */
    public void rotate(int[][] matrix) {
        int rows = matrix.length;
        int width = rows; // 螺旋的宽度
        while (width > 1) {
            int row = (rows - width) / 2;// 起始结点坐标
            int col = row;// 起始结点坐标
            // 螺旋顺时针移动 width-1个位置
            for (int i = 0; i < width - 1; i++) {
                int tmp = matrix[row][col + i];
                matrix[row][col + i] = matrix[row + width - 1 - i][col];
                matrix[row + width - 1 - i][col] = matrix[row + width - 1][col + width - 1 - i];
                matrix[row + width - 1][col + width - 1 - i] = matrix[row + i][col + width - 1];
                matrix[row + i][col + width - 1] = tmp;
            }
            width -= 2;
        }
    }
    
    /**
     * 8. 字符串转换整数 (atoi)
     * 
	 * 请你来实现一个 atoi 函数，使其能将字符串转换成整数。
	 * 
	 * 首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
	 * 
	 * 当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
	 * 
	 * 该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
	 * 
	 * 注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
	 * 
	 * 在任何情况下，若函数不能进行有效的转换时，请返回 0。
	 * 
	 * 说明：
	 * 
	 * 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231,  231 − 1]。如果数值超过这个范围，qing返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。
	 * 
	 * 示例 1:
	 * 
	 * 输入: "42"
	 * 输出: 42
	 * 示例 2:
	 * 
	 * 输入: "   -42"
	 * 输出: -42
	 * 解释: 第一个非空白字符为 '-', 它是一个负号。
	 *      我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
	 * 示例 3:
	 * 
	 * 输入: "4193 with words"
	 * 输出: 4193
	 * 解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
	 * 示例 4:
	 * 
	 * 输入: "words and 987"
	 * 输出: 0
	 * 解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
	 *      因此无法执行有效的转换。
	 * 示例 5:
	 * 
	 * 输入: "-91283472332"
	 * 输出: -2147483648
	 * 解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
	 *      因此返回 INT_MIN (−231) 。
     * @param str
     * @return
     */
    public int myAtoi(String str) {
        if (str == null) {
            return 0;
        }
        int len = str.length();
        int i = 0;
        while (i < len && str.charAt(i) == ' ') {
            // 忽略前置的空格
            i++;
        }
        if (i >= len) {
            return 0;
        }
        boolean negitive = false;
        StringBuilder numsBuilder = new StringBuilder();
        char ch = str.charAt(i);
        if (!(ch == '+' || ch == '-' || (ch >= '0' && ch <= '9'))) {
            // 第一位有效位非法
            return 0;
        }
        if (ch == '+' || ch == '-') {
            negitive = (ch == '-');
            while (i < len - 1 && str.charAt(i + 1) == '0') {
                i++;
            }
        } else {
            if (ch != '0') {
                numsBuilder.append(str.charAt(i));
            } else {
                while (i < len - 1 && str.charAt(i + 1) == '0') {
                    i++;
                }
            }
        }
        ++i;
        if (i < len) {
            ch = str.charAt(i);
            while (ch >= '0' && ch <= '9') {
                numsBuilder.append(ch);
                ++i;
                if (i < len) {
                    ch = str.charAt(i);
                } else {
                    break;
                }
            }
        }
        String numStr = numsBuilder.toString();
        if (numStr.length() > 0) {
            int strLen = numStr.length();
            int maxLen = String.valueOf(Integer.MAX_VALUE).length();
            if (strLen > maxLen || (strLen == maxLen && (Long.valueOf(Integer.MAX_VALUE) < Long.valueOf(numStr)
                    || Long.valueOf(Integer.MIN_VALUE) > Long.valueOf(numStr)))) {
                if (negitive) {
                    return Integer.MIN_VALUE;
                } else {
                    return Integer.MAX_VALUE;
                }
            } else {
                return negitive ? -Integer.parseInt(numStr) : Integer.parseInt(numStr);
            }
        }
        return 0;
    }
    
    /**
     * 540. 有序数组中的单一元素
     * 
	 * 给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
	 * 
	 * 示例 1:
	 * 
	 * 输入: [1,1,2,3,3,4,4,8,8]
	 * 输出: 2
	 * 示例 2:
	 * 
	 * 输入: [3,3,7,7,10,11,11]
	 * 输出: 10
	 * 注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。
     * @param nums
     * @return
     */
    public int singleNonDuplicate(int[] nums) {
        int ret = 0;
        for (int num : nums) {
            ret ^= num;
        }
        return ret;
    }
 
    /**
     * 442. 数组中重复的数据
     * 
	 * 给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。
	 * 
	 * 找到所有出现两次的元素。
	 * 
	 * 你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？
	 * 
	 * 示例：
	 * 
	 * 输入:
	 * [4,3,2,7,8,2,3,1]
	 * 
	 * 输出:
	 * [2,3]
     * @param nums
     * @return
     */
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> list = new ArrayList<Integer>();
        int i = 0;
        // 通过一趟遍历，交换，使nums[0...len-1]分别存1...N。
        while (i < nums.length) {
            int num = nums[i];
            if (num == 0 || num == i + 1) {
                i++;
                continue;
            }
            if (nums[num - 1] == num) {
                list.add(num);
                nums[i] = 0;
                i++;
            } else {
                // 交换 i 和 nums[i]-1 两个位置上的数字
                nums[i] = num ^ nums[num - 1];
                nums[num - 1] = nums[i] ^ nums[num - 1];
                nums[i] = nums[i] ^ nums[num - 1];
            }
        }
        return list;
    }
}
